I've been asked to help write some code to assist in flight planning
by choosing routes. I have just enough Computer Science and IFR
background to make me dangerous. I said that I'd donate my effort
if it results in Free code the community can use. So we're making
this a community project.

Although this sounds like a fairly simple task, performed by DUAT(S)
and IFR students daily, there are a lot of complexities and I suspect
that there are lots of opportunities for the community to optimize
the process. Here's are some of my thoughts to kick around.

All the data we need should be in the FAA ATA-100 collection.
http://aviationtoolbox.org/old/ATA-100/
Flights will mostly be along airways.
http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Awy_rf.txt
Preferred routes should be used when possible.
http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Pfr_rf.txt
Transitions between airports and airways will be handled with
standard arrival and departure procedures when possible.
http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Stardp_rf.txt

Here's a simple-minded algorithm with lots of holes to fill.

Provide start and end airports and altitude
restrictions.

Get started with a standard departure or create one.

Use preferred route or create one using least cost
(mileage) routing. There are 20,757 airways.

Finish using a standard approach or create one.

So...suggestions?

Thank you.

--kyler

In a previous article, Kyler Laird > said:
>Here's a simple-minded algorithm with lots of holes to fill.
>
> Provide start and end airports and altitude
> restrictions.
>
> Get started with a standard departure or create one.
>
> Use preferred route or create one using least cost
> (mileage) routing. There are 20,757 airways.
>
> Finish using a standard approach or create one.
>
>So...suggestions?

I started playing around with this idea years ago before when I was going
to write an on-line flight planner. (That was an idea I started work on
and then abandoned, and then a year or two later when I discovered CoPilot
I decided that this was a better use of all the FAA data I had collected.)

What I thought I'd do for the first cut at the algorithm was:
Find every VOR that's within "X" degrees of a straight line between
the start and end

At that VOR

- Find every VOR that's within "X" degrees of a straight line between
that VOR and the end point.

- Continue iterating until there are no VORs between you and the end
point.

When you have all your candidate routes, throw away any that don't
have airways between the VOR. Maybe make an exception if the distance is
less than "Y". Sort from shortest to longest.

Obviously that needs some work to handle DPs and STARs and preferred
routes.


--
Paul Tomblin > http://xcski.com/blogs/pt/
Today Has Been Two Of Those Days.
-- Mike Andrews

Paul Tomblin wrote:

> In a previous article, Kyler Laird > said:
>
>>Here's a simple-minded algorithm with lots of holes to fill.
>>
>> Provide start and end airports and altitude
>> restrictions.
>>
>> Get started with a standard departure or create one.
>>
>> Use preferred route or create one using least cost
>> (mileage) routing. There are 20,757 airways.
>>
>> Finish using a standard approach or create one.
>>
>>So...suggestions?
>
>
> I started playing around with this idea years ago before when I was going
> to write an on-line flight planner. (That was an idea I started work on
> and then abandoned, and then a year or two later when I discovered CoPilot
> I decided that this was a better use of all the FAA data I had collected.)
>
> What I thought I'd do for the first cut at the algorithm was:
> Find every VOR that's within "X" degrees of a straight line between
> the start and end
>
> At that VOR
>
> - Find every VOR that's within "X" degrees of a straight line between
> that VOR and the end point.
>
> - Continue iterating until there are no VORs between you and the end
> point.
>
> When you have all your candidate routes, throw away any that don't
> have airways between the VOR. Maybe make an exception if the distance is
> less than "Y". Sort from shortest to longest.
>
> Obviously that needs some work to handle DPs and STARs and preferred
> routes.

I'd think some of the approaches taught in any good operations research
course would be much better. It's been 20+ years since I took my last
OR course, but I'd look into a good OR text before writing code. There
a much better methods than a brute force, exhaustive search approach.


Matt

> All the data we need should be in the FAA ATA-100 collection.
> http://aviationtoolbox.org/old/ATA-100/
> Flights will mostly be along airways.
> http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Awy_rf.txt
> Preferred routes should be used when possible.
> http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Pfr_rf.txt
> Transitions between airports and airways will be handled with
> standard arrival and departure procedures when possible.
> http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Stardp_rf.txt
>

Excuse my ignorance, but what is http://aviationtoolbox.org ?

Lots of good data there but not so much as a readme to explain who/why. I
recently bought a copy of the FAA database disc from ATA-100 in order to play
with my own flight planning application -- now it appears that I could have
downloaded it from http://aviationtoolbox.org. Cool.

>>
Preferred routes should be used when possible.

So...suggestions?
<<

Find out what the =real= preferred routes are. They are not published. They
are in the hands of the approach controllers. On the East Coast (where I fly)
the preferred routes are almost never given (to me), but rather, other routes
which seem to be standard are.

Jose


--
(for Email, make the obvious changes in my address)

In a previous article, said:
>Lots of good data there but not so much as a readme to explain who/why. I
>recently bought a copy of the FAA database disc from ATA-100 in order to play
>with my own flight planning application -- now it appears that I could have
>downloaded it from http://aviationtoolbox.org. Cool.

Yeah, it's pretty sucky that the FAA wants $36 to make a CD (and ship it
FedEx), when there is so little data and so few people who care that it's
easy to share it out over a measly cable modem upload.

I have the CD subscription, and I make it available to a number of people
who download it from me every 56 days when I get the new one.

--
Paul Tomblin > http://xcski.com/blogs/pt/
"You are all but subwidgets in a composite container whose logical tab
group I have registered the traversal order of. I can merely point at you
and your popup dialogue will be unmapped unless XmNautoUnmanage is False."

In article >,
Kyler Laird > wrote:
>Flights will mostly be along airways.
> http://aviationtoolbox.org/old/ATA-100/Subscriber_File_Formats/Awy_rf.txt

I keep meaning to apply Dijkstra's algorithm to airway routing.
The key will be choosing edge costs.

>Preferred routes should be used when possible.
>Transitions between airports and airways will be handled with
>standard arrival and departure procedures when possible.

You can do this all with appropriate costs assigned to the routes and
transitions that you want. The tricky part is weighting thoses costs
properly against whatever you consider to be overriding factors (eg
forecast winds, icing, aircraft performance, distance, available nav
equipment, ...)

--
Ben Jackson
>
http://www.ben.com/

(Teacherjh) writes:

>Find out what the =real= preferred routes are. They are not published. They
>are in the hands of the approach controllers. On the East Coast (where I fly)
>the preferred routes are almost never given (to me), but rather, other routes
>which seem to be standard are.

Yeah, this is the kind of "community optimization" I think could be a
big part of such an undertaking. If everyone starts contributing routes
that "seem to be standard", the system would be able to better match what
is likely to be granted. Managing such data is quite a task but I like
the thought of being able to use it.

'course I also want to assign higher route costs to airways that traverse
active MOAs, etc.

--kyler

"Ben Jackson" > wrote in message
news:tCmbd.121529$He1.75934@attbi_s01...
>
> I keep meaning to apply Dijkstra's algorithm to airway routing.
> The key will be choosing edge costs.

I tried something similar for Western Europe. Thinking aloud... My
algorithm was basically:

a) load the entire airway network as a graph using distances as costs
b) link airports to the network using SIDs and STARs (important in Europe,
probably less so in US)
c) add preferred routes using the a cost of
start_to_end_great_circle_distance * factor, where factor is just less than
1.
d) run Dijkstra's algorithm (I was doing this in Perl so I just used the
Graph module from CPAN) for a departure airport
e) store the least cost routing from the departure airport to everywhere
else in a database

Repeat for other departure airports of interest. Processing time for one
departure airport for my network was about 30s on a fairly typical desktop
machine. YMMV, literally. ;-)

Provided your airway network only changes every 28 days (can't speak for the
US but that's what happens in the rest of the world for aeronautical data),
you've then got "static" routes valid for a month which means that to run
this for 100 airports or so, it should be a case of "do the calculation once
and store the results".

> You can do this all with appropriate costs assigned to the routes and
> transitions that you want. The tricky part is weighting thoses costs
> properly against whatever you consider to be overriding factors (eg
> forecast winds, icing, aircraft performance, distance, available nav
> equipment, ...)

Adding dynamic issues is not only difficult from a "what cost factor do I
use?" point of view, but actually affects the entire strategy. Calculating
weighted factors based on winds means that you have to do a calculation for
the entire network (you may be able to preload the network, but you still
have to run a weighting factor calc for each edge) which is likely to be
very time consuming. You then have to run Dijkstra's algorithm to get the
least-cost routes. But now we're doing that for *every* flight, which means
that we wait for both steps of the processing (edge costs + Dijkstra)
instead of doing a database lookup on stuff that's run once a month.

I wondered about a middle ground. If you could store the 10 or even 100
least-cost routes for a particular airport-pair, then running those routes
for a single flight would be relatively quick (either individually or doing
Dijkstra on the much reduced network). But Dijkstra doesn't produce the
runners up, only the winner, so how do we find the set of 10 or 100 routes
to consider? Do you knock out legs and run the algorithm again? If so,
which ones?

Reducing the network to waypoints within x miles of the great circle for a
particular flight (a little like Paul Tomblin's suggestion) is one
possibility, but, at least in Europe, x would have to be pretty big. On a 3
hour trip to Germany from my home base in the UK, I basically have the
choice between an initial route that goes east over Holland, or south and
then south east over Belgium. For a 450 mile route, I have to consider a
band of possibilities at least 150 miles wide.

Anyway, just sharing some thinking.

Julian Scarfe

"Julian Scarfe" > writes:

>"Ben Jackson" > wrote in message
>news:tCmbd.121529$He1.75934@attbi_s01...
>>
>> I keep meaning to apply Dijkstra's algorithm to airway routing.

That was my first thought...'course it's about all I remember about
network theory...

>> The key will be choosing edge costs.

What's the difficulty here? The airway file contains distances.
Are we not treating airways as the network edges?

>I tried something similar for Western Europe. Thinking aloud... My
>algorithm was basically:

>a) load the entire airway network as a graph using distances as costs
>b) link airports to the network using SIDs and STARs (important in Europe,
>probably less so in US)
>c) add preferred routes using the a cost of
>start_to_end_great_circle_distance * factor, where factor is just less than
>1.

Hmmmm...I like that. It would allow for lots of tweaking too.

>d) run Dijkstra's algorithm (I was doing this in Perl so I just used the
>Graph module from CPAN) for a departure airport
>e) store the least cost routing from the departure airport to everywhere
>else in a database

>Repeat for other departure airports of interest. Processing time for one
>departure airport for my network was about 30s on a fairly typical desktop
>machine. YMMV, literally. ;-)

I wasn't planning to do a lot of precomputation. When we get into altitude
restrictions it just gets too complicated. The shortest path for me from
Indiana to California is going to be much different than for someone who is
going to stay below 8,000'. Besides altitude restrictions, I can imagine
wanting to specify avoidance of MOAs, long overwater segments, busy
airspace, etc.

>Adding dynamic issues is not only difficult from a "what cost factor do I
>use?" point of view, but actually affects the entire strategy. Calculating
>weighted factors based on winds means that you have to do a calculation for
>the entire network

Oh, yeah...winds too.

>(you may be able to preload the network, but you still
>have to run a weighting factor calc for each edge) which is likely to be
>very time consuming. You then have to run Dijkstra's algorithm to get the
>least-cost routes. But now we're doing that for *every* flight, which means
>that we wait for both steps of the processing (edge costs + Dijkstra)
>instead of doing a database lookup on stuff that's run once a month.

It's not clear to me that this is a terrible burden. A student
sitting in front of enroute charts can figure out reasonable solutions
so I assume I can program a computer to do the same in short order.

I think that learning to disregard edges that aren't of interest is
the key. This seems fairly simple at first but in mountainous regions
with low altitude restrictions it could get difficult because you might
need to go far away from a direct route.

>Reducing the network to waypoints within x miles of the great circle for a
>particular flight (a little like Paul Tomblin's suggestion) is one
>possibility, but, at least in Europe, x would have to be pretty big. On a 3
>hour trip to Germany from my home base in the UK, I basically have the
>choice between an initial route that goes east over Holland, or south and
>then south east over Belgium. For a 450 mile route, I have to consider a
>band of possibilities at least 150 miles wide.

This doesn't sound so bad to me. I don't have a grasp on the power
required to solve it though.

>Anyway, just sharing some thinking.

Indeed! I appreciate the thoughts!

--kyler

Kyler Laird wrote:

> It's not clear to me that this is a terrible burden. A student
> sitting in front of enroute charts can figure out reasonable solutions
> so I assume I can program a computer to do the same in short order.

I always got stuck at trying to find a reasonable choice for the node at which
the enroute structure should be entered and exited. Once you pick the end points
(where to enter and leave) the choice of routes is just an OR optimization
problem, as others have noted.

>
> I think that learning to disregard edges that aren't of interest is
> the key. This seems fairly simple at first but in mountainous regions
> with low altitude restrictions it could get difficult because you might
> need to go far away from a direct route.

Perhaps altitude requirements need to be included in the costs.

Dave

I like the idea of running the script once a month, but for 20.00
airports this would be a quite database.

Another idea is when we have found preferred routes, also store use
routes (routes that user knows he/she will get from atc after filin
different route)... mainly for busy areas NY etc... atc's ow
prefferred routing as previously mentioned.

We will be using mapserver with this project and use mysql for db.
Php or cgi script for this would be nice


http://www.v1rotate.com
View this thread: http://www.v1rotate.com/portal/forums/showthread.php?threadid=9334

In article >,
Julian Scarfe > wrote:
>Repeat for other departure airports of interest. Processing time for one
>departure airport for my network was about 30s on a fairly typical desktop
>machine. YMMV, literally. ;-)

I think you can do better than that by ordering your edges better. You
know more than just edge costs, you also have coordinates for each node.
You can choose to explore edges that move you closer to the destination
first.

IIRC, the key to making Dijkstra fast is to find a solution as early as
possible. That establishes a baseline cost that allows massive pruning
of the search space.

>least-cost routes. But now we're doing that for *every* flight, which means
>that we wait for both steps of the processing (edge costs + Dijkstra)
>instead of doing a database lookup on stuff that's run once a month.

Right. But if I'm going to do the work then I want it to calculate all
of the factors that I would, given infinite time and patience on my part.

--
Ben Jackson
>
http://www.ben.com/

http://rfinder.asalink.net/free/

I found that for simmers, but this is as close as I hope for.

Would be a nice to see a source for that .cgi ;)

Hank

> In article >,
> Julian Scarfe > wrote:
> >Repeat for other departure airports of interest. Processing time for one
> >departure airport for my network was about 30s on a fairly typical
desktop
> >machine. YMMV, literally. ;-)

"Ben Jackson" > wrote in message
news:rTzbd.249118$D%.142632@attbi_s51...
>
> I think you can do better than that by ordering your edges better. You
> know more than just edge costs, you also have coordinates for each node.
> You can choose to explore edges that move you closer to the destination
> first.
>
> IIRC, the key to making Dijkstra fast is to find a solution as early as
> possible. That establishes a baseline cost that allows massive pruning
> of the search space.

That may be the case. I should have said that what I was trying to do was
create a server-based system for large numbers of users with different
dep-dest pairs. In that case, I'm looking at all potential destinations in
parallel. The strategy for a client-based system starting from scratch for
every single flight might be rather different.

Julian

"Julian Scarfe" > wrote in message >...
> "Ben Jackson" > wrote in message
> news:tCmbd.121529$He1.75934@attbi_s01...
> >
> > I keep meaning to apply Dijkstra's algorithm to airway routing.
> > The key will be choosing edge costs.
>
> I tried something similar for Western Europe. Thinking aloud... My
> algorithm was basically:
>
> a) load the entire airway network as a graph using distances as costs

*** I would modify that to use a combination of distance and MEA as
the cost.
I've found that in my personal flight planning, lower MEAs often
translate into a better flight, even if they involve a bit of a
dogleg.

- Jerry Kaidor ( )

Y'all,
My IFR is usually in the SF Bay Area. I have found that the preferred
routes take me miles out of my way. I have also found that a brief
negotiated change of route suc as direct to a fix that
cuts 30-40 miles off the preferred airways is justified.

Consider IFR to Las Vegas. MEA 16K or above. Even 13K
takes you all the way around Edwards. Negotiated changes work
if known and used.

I would suggest that at some point an indicator on the system would
tell the pilot that it is time to negotiate a change.

Gene Whitt

I always understand better with pictures ;)

This is how I understand how this thingy works.

http://www.v1rotate.com/images/navmap.gif

basically draw 3 boxes and do all the calculations inside within these
boxes. This will limit the fixes to calculate.
Limit area #1 for your origin, area #2 for your destination (allow fixes to
be within these boxes so they can join to airways.)
Limit area #3 for route (Only vor's within airways)

KBWI
EMI
J211
JERES
J211
BUSTR
J211
LEONI
J211
JST
J152
AVERE
KPIT

jeres bustr and leoni could be dropped, since they are on same airways

KBWI
EMI
J211
JST
J152
AVERE
KPIT


Here is another link that might interest or help us within this project.
http://gis.vegcrew.net/cgi-bin/viewcvs.cgi/VegGIS/router/build_route.pl?rev=1.1.1.1&view=markup

Hank

"v1rotate dot com" > writes:

>basically draw 3 boxes and do all the calculations inside within these
>boxes. This will limit the fixes to calculate.

It's not clear to me that these regions can be adequately chosen from the
start (especially for long flights) but it certainly would simplify things.

>Limit area #1 for your origin, area #2 for your destination (allow fixes to
>be within these boxes so they can join to airways.)

I think these will need to extend well beyond the endpoints. As a worst
case example, consider a trip to an airport just on the other side of a
mountain that is too high to traverse directly.

>jeres bustr and leoni could be dropped, since they are on same airways

Dropping seems dangerous. What if one of those dropped waypoints is close
to your destination? Will you pick that up later?

--kyler

Dropping I mean could be dropped from processing, since they are on the
airways db...
No need to process fixes, if they are already in the airways list. They are
still listed, but not processed.
Only start and end of the airways are processed.

Extend as far as needed. (ie 250 miles from centerline... no need to
calculate fixes beyond this unless you wanted to.)

Just wanted to spark up the discussion ;)

Hank